package cn.njupt.cmpSort;


public class HeapSort<E extends Comparable<E>> extends Sort<E>{
    private int heapsize;
    @Override
    public void sort() {
        heapsize=array.length;
        heapify();

        while(heapsize>1){
            swap(0,--heapsize);
            siftDown(0);
        }

    }



    private void heapify(){
        //自下而上的下滤
        int size=(heapsize>>1)-1;
        for (int i = size; i >=0; i--) {
            siftDown(i);
        }
    }

    private void siftDown(int index) {
        E initalValue= array[index];
        int half=heapsize>>1;
        while(index<half){
            //默认比较左孩子节点
            int childIndex=(index<<1)+1;

            int rightIndex=childIndex+1;
            childIndex=((rightIndex<heapsize) && (cmpElements(array[rightIndex],array[childIndex])>0))?rightIndex:childIndex;
            if(cmpElements(array[childIndex],initalValue)<0)break;

            array[index]=array[childIndex];
            index=childIndex;
        }
        array[index]=initalValue;

    }

}
